Cyclic scheduling in robotic flowshops with bounded work‐in‐process levels

This study addresses cyclic scheduling in robotic flowshops with bounded work‐in‐process (WIP) levels. The objective is to minimize the cycle time or, equivalently, to maximize the throughput, under the condition that the WIP level is bounded from above by a given integer number. We present several strongly polynomial algorithms for the 2‐cyclic robotic flowshop scheduling problems for various WIP levels. © 2010 Wiley Periodicals, Inc. Naval Research Logistics 58: 1–16, 2011     

科学工作流技术研究综述

科学工作流管理系统(Scientific Workflow Management Systems,SWfMS)为科学家提供一个管理大规模复杂科学计算的有效平台,通过管理复杂应用程序对海量科学数据进行管理、分析、仿真和可视化以帮助科学家进行科学发现.本文首先对科学工作流(Scientific Workflow,SWF)...     

基于逆向分层的工作流时间-费用优化方法

针对效用网格下基于优先级因子的工作流时间-费用优化问题,基于工作流的同步完成特征对任务进行分层并提出三种实时调度算法:基于逆向分层的sufferage(BLSuff)、基于逆向分层的min-min(BLMin)及基于逆向分层的min-max(BLMax)。算法设计基于优先级因子的衡量标准对时间与费用同时进行优化,并为任务设置期望完成时间以达到充分利用费用优化空间进行费用优化的目标。实验结果表明这三种算法在各种优先级因子下都能对工作流的执行时间与执行费用进行较好的优化。     

防空监视网络传感器资源分配的最优化

针对防空监视网络的传感器管理问题,讨论了传感器资源分配的最优化方法。提出了把传感器资源分配问题映射为多代理系统分布约束最优化问题的解决策略,设计了基于约束代价下界搜索的异步分枝定界最优化算法,实现了传感器资源分配问题最优解的异步并行搜索,给出的仿真实例说明了传感器资源分配最优化方法的有效性。     

Cyclic preference scheduling for nurses using branch and price

This paper presents a new methodology to solve the cyclic preference scheduling problem for hourly workers. The focus is on nurse rostering but is applicable to any organization in which the midterm scheduling decision must take into account a complex of legal, institutional, and preferential constraints. The objective is to strike a balance between satisfying individual preferences and minimizing personnel costs. The common practice is to consider each planning period independently and to generate new rosters at the beginning of each. To reduce some of the instability in the process, there is a growing trend toward cyclic schedules, which are easier to manage and are generally perceived to be more equitable. To address this problem, a new integer programming model is presented that combines the elements of both cyclic and preference scheduling. To find solutions, a branch‐and‐price algorithm is developed that makes use of several branching rules and an extremely effective rounding heuristic. A unique feature of the formulation is that the master problem contains integer rather than binary variables. Computational results are reported for problem instances with up to 200 nurses. Most were solved within 10 minutes and many within 3 minutes when a double aggregation approach was applicable. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007.     

Parallel machine scheduling with job assignment restrictions

In the classical multiprocessor scheduling problem independent jobs must be assigned to parallel, identical machines with the objective of minimizing the makespan. This article explores the effect of assignment restrictions on the jobs for multiprocessor scheduling problems. This means that each job can only be processed on a specific subset of the machines. Particular attention is given to the case of processing times restricted to one of two values, 1 and λ, differing by at most 2. A matching based polynomial time ε‐approximation algorithm is developed that has a performance ratio tending to . This algorithm is shown to have the best possible performance, tending to 3/2, for processing times 1 and 2. For the special case of nested processing sets, i.e., when the sets of machines upon which individual jobs may be assigned are non‐overlapping, the behavior of list scheduling algorithms is explored. Finally, for assignment restrictions determined by just one characteristic of the machines, such as disc storage or memory constraint in the case of high performance computing, we contribute an algorithm that provides a 3/2 worst case bound and runs in time linear in the number of jobs. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

卫星数传调度模型研究

卫星数传调度问题是一个具有多时间窗口、多资源约束的优化问题。针对该问题,建立了卫星数传需求模型、任务模型和调度模型。在建模过程中,采用了框架模型形式,把问题中的主要约束封闭于每个数传任务中,这在降低调度模型复杂度的同时,也降低了调度算法设计难度。还提出了调度算法设计思想,并设计了一基于灵活度的调度算法。仿真表明,所建立的模型及算法对解决卫星数传调度问题是可行的。     

军事攻防中的多属性资源分配对策模型

针对资源受限情形下的两阶段攻防资源分配问题,提出一种基于多属性决策的资源分配对策模型。防守者首先将有限的防护资源分配到不同的目标上,继而进攻者选择一种威胁组合方式对目标实施打击。基于博弈论相关知识,模型的求解结果可以使防守者最小化自身损失,使进攻者最大化进攻收益。同时,针对模型的特点,给出了一些推论和证明。通过一个示例验证了模型的合理性以及相关推论的准确性,能够为攻、防双方规划决策提供辅助支持。     

Mean sojourn times in multiclass feedback queues with gated disciplines

In this paper, we investigate multiclass feedback queues with gated disciplines. The server selects the stations by a nonpreemptive priority scheduling algorithm and serves customers in the selected station by either a gated FCFS discipline or a gated priority discipline. We take a rather systematic approach to their mean sojourn times. We define conditional expected sojourn times for all customers and derive their expressions from an analysis of busy periods. Since they are shown to be linear in some components of the system states, their steady state mean values can be derived from simple limiting procedures. These mean values can be obtained from a set of linear equations. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 719–741, 2003.     

CON/SLK due date assignment and scheduling on a single machine with two agents

We consider scheduling problems involving two agents (agents A and B), each having a set of jobs that compete for the use of a common machine to process their respective jobs. The due dates of the A‐jobs are decision variables, which are determined by using the common (CON) or slack (SLK) due date assignment methods. Each agent wants to minimize a certain performance criterion depending on the completion times of its jobs only. Under each due date assignment method, the criterion of agent A is always the same, namely an integrated criterion consisting of the due date assignment cost and the weighted number of tardy jobs. Several different criteria are considered for agent B, including the maxima of regular functions (associated with each job), the total (weighted) completion time, and the weighted number of tardy jobs. The overall objective is to minimize the performance criterion of agent A, while keeping the objective value of agent B no greater than a given limit. We analyze the computational complexity, and devise polynomial or pseudo‐polynomial dynamic programming algorithms for the considered problems. We also convert, if viable, any of the devised pseudopolynomial dynamic programming algorithms into a fully polynomial‐time approximation scheme. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 416–429, 2016